Target Sum
Let's solve the Target Sum problem using Dynamic Programming.
Statement#
Given an array of positive integers arr and a target T, build an expression using these numbers by inserting a T.
For example, consider an array [1, 1] and a target 0, we can build the following expressions:
Expression | Sum |
+ 1 + 1 | 2 |
+ 1 – 1 | 0 |
– 1 + 1 | 0 |
– 1 – 1 | –2 |
The total number of expressions that evaluate to the target are 2.
Constraints:
arr.lengtharr[i]sum(arr[i])T
Examples#
No. | arr | T | Number of Expressions |
1 | [1, 2, 1] | 0 | 2 |
2 | [1, 1, 1, 1] | 2 | 4 |
Try it yourself#
Implement your solution in the following playground.
Note: If you clicked the "Submit" button and the code timed out, this means that your solution needs to be optimized in terms of running time.
Hint: Use dynamic programming and see the magic.
Solution#
We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.
Naive approach#
A naive approach to this problem is to find all expressions using the given numbers and then count the number of expressions that evaluate to the given target.
For example, we have an array [2, 1, 2], and we can build the following expressions:
Now, for a given target, we can count the number of expressions that evaluate to that target. For example, if the target is –1, we can count that 2 expressions evaluate to –1.
The calculation above shows that we need a recursive solution to make all possible expressions. In other words, we divide the problem into subproblems, and for each number, we place a
Let’s implement the algorithm as discussed above:
Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.
Time complexity#
The time complexity of the naive approach is
Space complexity#
As the maximum depth of the recursive call tree is
Optimized solution using dynamic programming#
Now, let us improve the recursive solution using top-down and bottom-up approaches.
Top-down solution#
The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array.
In the recursive solution, when we generate two new expressions by inserting a
This results in many redundant recursive calls. To avoid this, we create a lookup table called dp of dp[i][T], where i and T represent the index of the integer and the generated sum, respectively. At any later time, if we encounter the same expression, we can return the stored result from the table with an
Let’s implement the algorithm as discussed above:
Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.
Time complexity#
As we avoided redundant calculations by storing all the intermediate results in a lookup table, the time complexity of this approach is reduced to
Space complexity#
The space taken by the lookup table is
Bottom-up solution#
The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. Here, we will again create a lookup table of size
As we see in the code below, the algorithm iterates over all integers and for every possible target sum t, it checks if it was generated during the previous iterations i.e., if dp[i-1][total+t] > 0, where total is the sum of all elements of the array. If it was generated, two new expressions are considered by inserting a dp[i-1][total+t] is added to the values of dp[i][total+t+arr[i]] and dp[i][total+t-arr[i]].
Let’s look at the following illustration to get a better understanding of the solution:
1 of 20
2 of 20
3 of 20
4 of 20
5 of 20
6 of 20
7 of 20
8 of 20
9 of 20
10 of 20
11 of 20
12 of 20
13 of 20
14 of 20
15 of 20
16 of 20
17 of 20
18 of 20
19 of 20
20 of 20
Let's implement the algorithm as discussed above:
Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.
Time complexity#
The time complexity of this algorithm is
Space complexity#
The space complexity of this algorithm is
Can we do better?
We can further improve the bottom-up approach by using a two dimensional lookup table of size dp[i][j+arr[i]] and dp[i][j-arr[i]], we require the value of dp[i-1][j]. Therefore, there is no point in storing all the previous rows. Instead, we can start by filling the first row of the lookup table ourselves. For each subsequent row, we compute all the values using the first row and store them in the second row of the lookup table. Then, we replace the first row with the second one so it can be used in the next iteration.
The time complexity will remain the same,
Solving the 0/1 Knapsack Problem
Subset Sum